1. Field of the Invention
The present invention relates to an address decoding method and related apparatus, and more specifically, to an address decoding method and related apparatus which can decode a memory address rapidly by comparing if some specific bits of the given address match predetermined values.
2. Description of the Prior Art
Please refer to FIG. 1. FIG. 1 shows function blocks of a conventional computer 10. The computer 10, as a microprocessor system, comprising a CPU 12, a chip set 14, a memory 16, a display card 18, a monitor 20, peripheral devices 22, and a BIOS system 24.
The memory 16 usually comprises several memory modules such as memory modules 30A to 30D shown in FIG. 1. Memory modules 30A to 30D comprise a plurality of memory units 34. Each memory unit 34 stores one bit of data. To sum all memory units 34 in memory modules 30A to 30D, we get the total memory capacity of the memory 16. In modern technology, a memory module is usually implemented by an independent circuit, connected to the computer 10 through sockets to form the memory 16. Different memory modules have memory units of different capacity (each memory module could have different memory capacity). Generally speaking, memory units in the memory module are distributed in two memory ranks. For example, as shown in FIG. 1, memory module 30A has two memory ranks 32A and 32B. The control circuit 28 will control one memory rank with one control signal to read/write data. As shown in FIG. 1, control signals CSp0 and CSp1 correspond to two memory ranks 32A and 32B in memory module 30A respectively. Control signals CSp2 to CSp7 correspond to memory ranks of memory modules 30B, 30C, and 30D respectively.
As for assignment of the address of each memory unit in the memory 16, please refer to FIG. 2 (also FIG. 1). FIG. 2 shows the assigned memory unit addresses in the memory 16. As shown in FIG. 2, suppose that memory modules 30A to 30D have 2^25 (2 to the power of 25), 2^27, 2^28, and 2^26 memory units respectively. That is to say, the capacities of memory modules 30A to 30D are 32 Mbs, 128 Mbs, 256 Mbs and 64 Mbs. Here one Mbs (Megabits) represent 2^20 bits. After the computer is turned on, the control circuit 28 will assign the numerically-increased addresses to each memory unit of memory module 30A to 30D. Of course, the binary system is the basic numerical expression in digital logic. The address of each memory unit is also expressed in the binary system. For example, as shown in FIG. 2, the address of each memory unit is expressed by 32 bits of the binary system. The “0th” bit is the least significant bit and the “31st” bit is the most significant bit. After assignment of the address, the first memory unit of memory module 30A will be assigned to address 36A. The expression is “000 . . . 0” (all bits are 0). Then, the following addresses of each memory unit are increased sequentially. For instance, the address of the second memory unit, 36B, is expressed as “00 . . . 01” (only the 0th bit is 1). The address of the third memory unit, 36C, is expressed as “00 . . . 10” (only the 1st bit is 1). The other situations are similar. The address of the second memory unit from the last one of memory module 30A, 36D, (the (2^25−1)th memory unit) is “0 . . . 01 . . . 10” (the first to the 24th bits are 1 and the others are 0). The address of the last memory unit of memory module 30A, 36E, (the (2^25)th memory unit) is increased to “0 . . . 01 . . . 11” (the 0th to the 24th bits are 1 and the others are 0).
When the control circuit 28 assigns addresses, it takes all memory units of all memory modules in the memory 16 as one part. Thus when the control circuit 28 assigns an address to the memory module 30B, the address will be continuously increased from address 36E (the address of the last memory unit of memory module 30A). As shown in FIG. 2, the first memory unit of memory module 30B corresponds to address 310. The value of the address will be increased from address 36E by one, becoming “0 . . . 010 . . . 0” (only the 25th bit is “1”). This means that the memory unit is seen as the (2^25+1)th memory unit in the memory 16 of the (2^25+1)th memory unit counted from the first memory unit of memory module 30A. Similarly, the second memory unit of memory module 30B is seen as the (2^25+2)th memory unit in the memory 16. The address value of the memory unit, corresponding to address 311, is the addition of the value of address 310 and one, becoming “0 . . . 010 . . . 01” (only the 0th bit and the 25th bit are 1). Because there are 2^27 memory units in the memory module 30B, the last two memory units in the memory module 30B are the (2^25+2^27−1)th and the (2^25+2^27)th memory units in the memory 16. The addresses of these two memory units corresponding to 38C and 38D are increased to “0 . . . 01001 . . . 10” (the 1st to the 24th bits and the 27th bit are 1, and the others are 0) and “0 . . . 01001 . . . 1” (the 0th to the 24th bits and the 27th bit are 1, and the others are 0).
To deduce the other situations by the rules above, the address of the first memory unit, corresponding to address 42A, in memory module 30C (the third memory module) is the value of address 38D increased by 1, becoming “0 . . . 01010 . . . 0” (only the 25th and the 27th bits are 1). This expression represents that the memory unit is the (2^25+2^27+1)th one counted from the memory unit address 36A in the address 16. Similarly, the address of the 2^28th memory unit, address 42B, in memory module 30C is increased to “0 . . . 011001 . . . 1” (the 0th to 24th bits and the 28th bit are 1, and the others are 0). This expression represents that the memory unit is the (2^25+2^27+2^28)th one counted from the memory unit address 36A in memory 16. From the first and the last addresses of each memory module, an ending address can be determined. As shown in FIG. 2, because all address values of the memory units in memory module 30A are less than the value of the first address 310 in the memory module 30B, address 310 can be taken as the end of the memory module 30A, address 46A. Similarly, the address values of memory units in each memory module 30B (and memory module 30A) are less than the value of the least address, address 42A, in the memory module 30C. Therefore address 42A can be seen as the corresponding ending address, address 46B, in memory module 30B. The address values of the memory module 30C as well as memory modules 30A and 30B are all less than the corresponding ending address, address 46C, in memory module 30C (That is also the least address, address 44A, in memory module 30D). Finally, all addresses of memory module 30D are less than the ending address 46D. Notice that ending addresses 46A to 46D are the binary results of accumulating capacity of each memory module. For instance, the ending address 46A represents the amount of 2^25 in the binary system. It is also the memory capacity of memory module 30A (or the number of memory units in memory module 30A). The ending address 46B represents the amount of (2^25+2^27) in the binary system, meaning the total memory capacity of the memory modules 30A and 30B. The ending address 46C, representing (2^25+2^27+2^28) in the binary system, is the total capacity of the memory modules 30A, 30B, and 30C. Finally, ending address 46D, representing (2^25+2^27+2^28+2^26) in the binary system, is the total capacity of memory modules 30A, 30B, 30C, and 30D.
Please refer to FIG. 3 (and FIG. 1, 2). FIG. 3 illustrates the diagram of the conventional method in which the control circuit 28 decodes addresses. In the control circuit 28 there are a buffer module 51, a plurality of subtraction modules 410 to 48D, and a logic module 50. The buffer module 51 stores the address 54 for transmitting data to the control circuit 28 from the CPU 12 (or other circuits). The control circuit 28 will decode the address. In the prior art, when the control circuit 28 decides what memory module a given address 54 belongs to after decoding, the control circuit 28 can implement functions of the subtraction modules 410 to 48D and logic module 50 by methods of hardware or software. The subtraction modules 410 to 48D are used to take a difference of the given address 54 and the ending addresses 46A to 46D (please also refer to FIG. 2). Relative magnitudes of the given address 54 and the ending addresses 46A to 46D are determined by the result of the subtraction operation. The result of the subtractor is processed by the logic module 50 to determine the memory module that the address 54 belongs to, and generate a corresponding decoded result 52. For example, if the given address 54 will be smaller than each ending address 46A to 46D. If the given address 54 belongs to memory module 30B, the given address 54 will be smaller than each ending address 46B to 46D, but not ending address 46A. Similarly, if the memory unit that the given address 54 corresponds to belongs to the memory module 30C, the given address 54 is only smaller than ending address 46D, but not ending addresses 46A to 46C. Each subtraction module 48A to 48D is used to reduce ending address 46A to 46D by the given address 54 so as to determine the magnitude between the given address 54 and ending address 46A to 46D. The logic module 50 determines the memory module that the given address 54 belongs to according to the results of subtraction module 410 to 48D. As shown in FIG. 3, if the given address 54 is “0 . . . 010010 . . . 0” (only the 25th and the 28th bit are “1”), it is not smaller than ending addresses 46A and 46B, but is smaller than ending addresses 46C and 46D. Thus, the logic module 50 can decide that the given address 54 corresponds to the memory unit of the memory module 30C.
Generally speaking, when control circuit 28 designates addresses, it will give sequentially increased addresses to memory units belonging to one memory rank. For example, if the 32 Mbs of memory module 30A are distributed in the memory ranks 32A and 32B (please refer to FIG. 1), the first 16 Mbs of addresses will be given to the memory units of the memory rank 32A and the second 16 Mbs addresses will be given to those of the memory rank 32B. In such kind of the address distribution, ending addresses which each memory rank corresponds to are defined. The conventional method described above is to determine the memory rank the given address 54 belongs to by comparing the given address and the ending address. Of course, in this application there will be eight memory ranks for the four memory modules, and there will be eight ending addresses. Eight subtraction modules are needed to compare the given addresses and each ending address.
However, in the prior art both the implementation of the subtraction module by hardware and by software programs of the north bridge circuit 26A do not have high efficiency. In the hardware method, implementing a subtraction module to subtract one binary number by another can make one number its complement to form a negative one, and then sum this negative number with the other. When a binary adder does summation between two binary numbers, it starts on the Least Significant Bit (LSB) of the two numbers. After the LSB is added, generating a carry bit, the second significant bit is added with the carry bit. Similarly, the following bits are added in turn.
When two binary numbers are added, the corresponding bits of two numbers as well as the carry bit from the previous calculation are needed to obtain the results. Thus, time during the addition is the accumulation of operation time of each digit. The more bits two binary numbers to be added have, the more time the addition will take. This characteristic of the addition is obvious in the prior art. If the subtraction module in FIG. 3 does subtraction to compare the magnitude of address 54 and each ending address 46A to 46D, it takes most of the time on subtraction, lacking efficiency of address decoding and operation of computer 10.